/*
 * @Author: szx
 * @Date: 2022-03-03 13:01:52
 * @LastEditTime: 2022-03-03 13:31:08
 * @Description:
 * @FilePath: \leetcode\500-599\576\576.js
 */
/**
 * @param {number} m
 * @param {number} n
 * @param {number} maxMove
 * @param {number} startRow
 * @param {number} startColumn
 * @return {number}
 */
// var findPaths = function (m, n, maxMove, startRow, startColumn) {
//     // dp 表示移动到当前坐标的所有路径数量和
//     const dp = new Array(maxMove + 1).fill(0).map(() => new Array(m).fill(0).map(() => new Array(n).fill(0)));
//     let res = 0;
//     const dirs = [
//         [-1, 0],
//         [1, 0],
//         [0, -1],
//         [0, 1]
//     ];
//     dp[0][startRow][startColumn] = 1;
//     const mod = 10 ** 9 + 7;
//     for (let i = 1; i <= maxMove; i++) {
//         for (let j = 0; j < m; j++) {
//             for (let k = 0; k < n; k++) {
//                 for (let dir of dirs) {
//                     const x = dir[0] + j;
//                     const y = dir[1] + k;
//                     if (x >= 0 && x < m && y >= 0 && y < n) {
//                         dp[i][j][k] += dp[i - 1][x][y];
//                         dp[i][j][k] %= mod;
//                     } else {
//                         res += dp[i - 1][j][k];
//                         res %= mod;
//                     }
//                 }
//             }
//         }
//     }
//     return res;
// };

var findPaths = function (m, n, maxMove, startRow, startColumn) {
    // dp 表示移动到当前坐标的所有路径数量和
    let dp = new Array(m).fill(0).map(() => new Array(n).fill(0));
    let res = 0;
    const dirs = [
        [-1, 0],
        [1, 0],
        [0, -1],
        [0, 1]
    ];
    dp[startRow][startColumn] = 1;
    const mod = 10 ** 9 + 7;
    for (let i = 1; i <= maxMove; i++) {
        const dpNew = new Array(m).fill(0).map(() => new Array(n).fill(0));
        for (let j = 0; j < m; j++) {
            for (let k = 0; k < n; k++) {
                for (let dir of dirs) {
                    const x = dir[0] + j;
                    const y = dir[1] + k;
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        dpNew[j][k] += dp[x][y];
                        dpNew[j][k] %= mod;
                    } else {
                        res += dp[j][k];
                        res %= mod;
                    }
                }
            }
        }
        dp = dpNew;
    }
    return res;
};
// console.log(findPaths(2, 2, 2, 0, 0));
console.log(findPaths(1, 3, 3, 0, 1));
